#include <iostream>
#include <vector>
#include <chrono>
#include <cstdint>
#include <omp.h>
#include <cstdlib>
#include <cstring>

// Structure to hold data
struct Data
{
  int id;
  int age;
  float weight;
  float height; // Additional attribute
  std::string name;
  std::string address;
  std::string email;
  std::string phone;
  std::string city;
  std::string country;
  int salary;
  int years_of_experience; // Additional attribute
  bool employed;           // Additional attribute
  float rating;            // Additional attribute
  float score;             // Additional attribute
};

// Compare function for std::sort by score
bool compare_score(const Data &a, const Data &b)
{
  return a.score < b.score;
}

// Validation function to check if the array is sorted correctly by score
bool validate_score(const std::vector<Data> &array)
{
  for (size_t i = 1; i < array.size(); i++)
  {
    if (array[i].score < array[i - 1].score)
      return false; // Array is not sorted correctly
  }
  return true; // Array is sorted correctly
}

// 快速排序的分区函数
int partition(std::vector<Data> &array, int low, int high)
{
  Data pivot = array[high]; // 选择最后一个元素作为枢轴
  int i = low - 1;          // 初始化较小元素的索引

  for (int j = low; j < high; j++)
  {
    if (compare_score(array[j], pivot))
    {
      i++;
      std::swap(array[i], array[j]); // 交换元素
    }
  }
  std::swap(array[i + 1], array[high]); // 将枢轴元素移到正确位置
  return i + 1;
}

// 快速排序函数
void quicksort(std::vector<Data> &array, int low, int high)
{
  if (low < high)
  {
    int pi = partition(array, low, high); // 分区索引

    quicksort(array, low, pi - 1); // 递归排序左子数组
    quicksort(array, pi + 1, high); // 递归排序右子数组
  }
}

// 合并两个已排序的子区间到一个临时数组中
void merge(std::vector<Data> &vec, std::vector<Data> &temp, size_t start1, size_t end1, size_t start2, size_t end2)
{
  size_t i = start1, j = start2, k = start1; // 初始化指针i, j和k

  // 合并两个子区间直到其中一个耗尽
  while (i < end1 && j < end2)
  {
    if (compare_score(vec[i], vec[j])) // 比较两个元素，选择较小的
    {
      temp[k++] = std::move(vec[i++]); // 将较小的元素移到临时数组中，并移动指针
    }
    else
    {
      temp[k++] = std::move(vec[j++]); // 将较小的元素移到临时数组中，并移动指针
    }
  }

  // 如果左子区间有剩余元素，全部移到临时数组中
  while (i < end1)
  {
    temp[k++] = std::move(vec[i++]);
  }

  // 如果右子区间有剩余元素，全部移到临时数组中
  while (j < end2)
  {
    temp[k++] = std::move(vec[j++]);
  }
}

// 并行排序函数，使用OpenMP进行并行处理
void parallel_sort(std::vector<Data> &array, uint64_t thread_size)
{
  // 计算每个线程应处理的数据块大小，确保所有数据项都能被分配
  uint64_t chunk_size = (array.size() + thread_size - 1) / thread_size;

  // 使用OpenMP并行对每个块进行排序
#pragma omp parallel for num_threads(thread_size)
  for (uint64_t i = 0; i < thread_size; ++i)
  {
    uint64_t start = i * chunk_size;                                      // 计算块的起始位置
    uint64_t end = std::min(start + chunk_size, array.size());            // 计算块的结束位置，避免越界
    quicksort(array, start, end - 1); // 对块进行排序
  }

  std::vector<Data> temp_array(array.size()); // 临时数组用于合并

  // 逐步合并排序好的块
  for (uint64_t step = 1; step < thread_size; step *= 2)
  {
    // 每次合并后块的大小增加一倍
#pragma omp parallel for num_threads(thread_size / step)
    for (uint64_t i = 0; i < thread_size; i += 2 * step)
    {
      uint64_t start1 = i * chunk_size;                                     // 第一个子区间的起始位置
      uint64_t end1 = std::min(start1 + chunk_size * step, array.size());   // 第一个子区间的结束位置
      uint64_t start2 = std::min(start1 + chunk_size * step, array.size()); // 第二个子区间的起始位置
      uint64_t end2 = std::min(start2 + chunk_size * step, array.size());   // 第二个子区间的结束位置

      if (start2 < end2) // 确保第二个子区间有元素
      {
        merge(array, temp_array, start1, end1, start2, end2); // 合并两个子区间
      }
    }
    array.swap(temp_array); // 交换原数组和临时数组，准备下一步合并
  }
}

int main(int argc, char *argv[])
{
  if (argc != 3)
  {
    std::cout << "Usage: " << argv[0] << " <array_size> <thread_size>" << std::endl;
    return 1;
  }

  uint64_t array_size = std::strtoull(argv[1], nullptr, 10);
  if (array_size == 0)
  {
    std::cout << "Array size must be a positive integer" << std::endl;
    return 1;
  }

  uint64_t thread_size = std::strtoull(argv[2], nullptr, 10);
  if (thread_size == 0)
  {
    std::cout << "Thread size must be a positive integer" << std::endl;
    return 1;
  }

  std::vector<Data> array(array_size);

  srand(time(NULL)); // Seed the random number generator
  for (uint64_t i = 0; i < array_size; i++)
  {
    array[i].id = i + 1;
    array[i].age = rand() % 100 + 1;                                  // Random age between 1 and 100
    array[i].weight = static_cast<float>(rand()) / RAND_MAX * 100.0f; // Random weight between 0 and 100
    array[i].height = static_cast<float>(rand()) / RAND_MAX * 200.0f; // Random height between 0 and 200
    array[i].name = "Name" + std::to_string(i);
    array[i].address = "Address" + std::to_string(i);
    array[i].email = "Email" + std::to_string(i) + "@example.com";
    array[i].phone = "+1234567890" + std::to_string(i);
    array[i].city = "City" + std::to_string(i);
    array[i].country = "Country" + std::to_string(i);
    array[i].years_of_experience = rand() % 30;                                        // Random years of experience between 0 and 29
    array[i].employed = rand() % 2;                                                    // Random employed status (0 or 1)
    array[i].rating = static_cast<float>(rand()) / RAND_MAX * 5.0f;                    // Random rating between 0 and 5
    array[i].score = static_cast<float>(rand()) / RAND_MAX * 11000000.0f - 1000000.0f; // Random score between -1000000 and 10000000
  }

  auto start_time = std::chrono::high_resolution_clock::now();

  if (thread_size == 1)
  {
    quicksort(array, 0, array.size() - 1);
  }
  else
    parallel_sort(array, thread_size);

  auto end_time = std::chrono::high_resolution_clock::now();
  double time_spent = std::chrono::duration_cast<std::chrono::duration<double>>(end_time - start_time).count();

  std::cout << "Time taken: " << time_spent << " seconds" << std::endl;

  if (validate_score(array))
    std::cout << "Validation: Array is sorted correctly by score" << std::endl;
  else
    std::cout << "Validation: Array is not sorted correctly by score" << std::endl;

  return 0;
}
